home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Set / Set.h < prev    next >
C/C++ Source or Header  |  1992-05-18  |  18KB  |  426 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/05/89 -- Initial design and implementation
  13. // Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
  14. // Updated: MBN 09/15/89 -- Added conditional exception handling
  15. // Updated: MBN 10/03/89 -- Fixed put() method to update value
  16. // Updated: MBN 10/07/89 -- Fixed double entry count with use of iterators
  17. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and changed
  18. //                          state from bit set to bit set/get macros
  19. // Updated: LGO 10/19/89 -- Fixed operator==() for tables with different bucket
  20. //                          count but same elements -- tables grew separately
  21. // Updated: MBN 12/22/89 -- Sprinkled "const" qualifiers all over the place!
  22. // Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
  23. // Updated: MBN 02/23/90 -- Made operators -=, ^=, |=, &= return reference 
  24. // Updated: MJF 03/12/90 -- Added group names to RAISE
  25. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  26. // Updated: VDN 02/21/92 -- New lite version
  27. //
  28. // The Set<Type> class implements a set  of elements  of a user-specified type.
  29. // This is accompilshed by using the parameterized type capability of C++.  The
  30. // Set<Type> class implements a simple one-element hash table where the key and
  31. // the value are the same thing.  The type of the Set class is the key/value in
  32. // the Hash Table.  The  Set<Type> class is  derived from the Hash_Table  class
  33. // and is  dynamic  in nature.  It's size   (ie. the number of  buckets  in the
  34. // table) is  always some prime number. Each  bucket holds 8 items.   No wholes
  35. // are left in a bucket; if a key/value is removed from the middle of a bucket,
  36. // following entries are moved up.   When a hash on a  key ends  up in a bucket
  37. // that is full, the table is enlarged.
  38. //
  39. // The private data  section of  a Set<Type> has  a  slot that   points  to the
  40. // physical memory allocated for some prime number of buckets each of which has
  41. // memory allocated for 8 items.  The number of buckets  currently in the table
  42. // is accessed by an index into a static table of  selected prime numbers. This
  43. // static table contained within  the class eliminates  the somewhat  expensive
  44. // runtime computation of prime numbers.  The  table consists of  prime numbers
  45. // where the difference  between  any two successive entries gets progressively
  46. // larger as you move through the table.  The specified range of primes results
  47. // in an arbitrary limitation of 2^22 entries in a single hash table.
  48. //
  49. // When a hash on a key ends up in a bucket that is full, the table is enlarged
  50. // to the next prime number of buckets or to the prime number  that is at least
  51. // large enough to accommodate  a user-specified growth  ratio. The  entries in
  52. // the  buckets are then  rehashed   into the   new  table.  Selection  of   an
  53. // appropriate hash function  is  crucial to  uniform  distribution through the
  54. // table. The default   hash  utilizes  the number   of  buckets  in order   to
  55. // accomplish this. A user-supplied function should do something similar.
  56. //
  57. // Other items in the private data section include a pointer to a hash function
  58. // and a  pointer to  a compare  function.   The compare   function  is used in
  59. // equality operations on key/value items.  The default compare function is the
  60. // built-in == operator.  The default  hash function is either a  simple 32 bit
  61. // value if sizeof(Type) is 4, that is shifted left  three bits with the result
  62. // modulo the number of buckets determining the  hash. This  is ideal when Type
  63. // is a pointer..   If sizeof(Type) is greater than  4,  then the 32 bit  value
  64. // used  is  the  result of  exclusive-oring  successive 32-bit values  for the
  65. // length of T1, and then applying the same  bit shift  and modulo operation as
  66. // before.
  67. //
  68. // Three different constructors are provided.  The  first  constructor takes no
  69. // arguments and creates  a  Set that can  contain 24 items before  resizing is
  70. // necessary.  The second constructor accepts an integer argument and creates a
  71. // Set that  can accomodate at  least the specified number  of items.  Finally,
  72. // the third constructor takes a single argument  consisting of a  reference to
  73. // another Set and duplicates its size and contents.
  74. //
  75. // Methods are provided to put, query,  and remove  an item from a set, perform
  76. // the  intersection, union,  difference, and exclusive-or  of two  sets, check
  77. // equality and inequality of  two set  objects, and determine if  one set is a
  78. // subset of another. In  addition, the notion of  a current position  within a
  79. // set is maintained and reset, next, previous,  find,  and get value functions
  80. // for setting and using the current position are provided.  Also  for use with
  81. // the current position are the next  union, next intersetion, next difference,
  82. // and next  exclusive-or  operations. These    allow a   user to access    the
  83. // first/next individual item that results  from some logical  operation. These
  84. // functions are particularly efficient, since no temporary Set<Type> structure
  85. // is created. Finally, functions to set the  compare and hash functions for an
  86. // instance of a set, get the count of the number of items in a set, output the
  87. // set to a stream, clear all elements from a set,  and determine if  a  set is
  88. // empty are also available.
  89. //
  90. // Use envelope to avoid deep copy and mutate in place.
  91.  
  92. #ifndef SETH                    // If no Set class,
  93. #define SETH                    // define it
  94.  
  95. #ifndef BASE_HASH_TABLEH            // If no Base Hash class
  96. #include <cool/Base_Hash.h>            // define it
  97. #endif
  98.  
  99. typedef long CoolSet_state;            // Current position state
  100.  
  101. template <class Type> CoolSet {
  102.   struct Type##_bucket {            // Structure for bucket
  103.     Type data[BUCKET_SIZE];
  104.   };
  105.   typedef Boolean (*Type##_CoolSet_Item_Compare) (const Type&, const Type&);
  106.   typedef long (*Type##_CoolSet_Hash) (const Type&);
  107.  
  108.   class CoolSet<Type>E;                // forward dec. of envelope
  109. }
  110.  
  111. template <class Type>
  112. class CoolSet<Type> : public CoolHash_Table {    // Define CoolSet
  113. public:
  114.   CoolSet<Type> ();                // Set of default size
  115.   CoolSet<Type> (unsigned long);        // Set for at least size
  116.   CoolSet<Type> (const CoolSet<Type>&);        // Set with reference
  117.   ~CoolSet<Type>();                // Destructor
  118.  
  119.   CoolSet<Type>& operator= (const CoolSet<Type>&); // Assignment
  120.   inline CoolSet<Type>& operator= (CoolSet<Type>E&); // Envelope back to set
  121.   
  122.   Boolean find (const Type&);            // Set current position
  123.   Type& value ();                // Get value at current
  124.   Boolean remove ();                // Remove item current position
  125.   
  126.   Boolean put (const Type&);            // Put element into set
  127.   Boolean remove (const Type&);            // Remove element from set
  128.   Boolean search (CoolSet<Type>&);        // Subset operator
  129.   Boolean resize (long);            // Resize for at least count
  130.   
  131.   CoolSet<Type>& operator|= (const CoolSet<Type>&);    // Union of two sets
  132.   CoolSet<Type>& operator-= (const CoolSet<Type>&);    // Difference of two sets
  133.   CoolSet<Type>& operator^= (const CoolSet<Type>&);    // Exclusive-or of two sets
  134.   CoolSet<Type>& operator&= (const CoolSet<Type>&);    // Intersection of two sets
  135.  
  136. //   Use envelope to avoid deep copy on return by value, and mutate in place
  137. //   inline friend CoolSet<Type> operator| (const CoolSet<Type>&,const CoolSet<Type>&);
  138. //   inline friend CoolSet<Type> operator- (const CoolSet<Type>&,const CoolSet<Type>&);
  139. //   inline friend CoolSet<Type> operator^ (const CoolSet<Type>&,const CoolSet<Type>&);
  140. //   inline friend CoolSet<Type> operator& (const CoolSet<Type>&,const CoolSet<Type>&);
  141.   
  142.   inline void set_union (const CoolSet<Type>&);    // Union of two sets       
  143.   inline void set_difference (const CoolSet<Type>&); // Difference of two sets  
  144.   inline void set_xor (const CoolSet<Type>&);         // Exclusive-or of two sets
  145.   inline void set_intersection (const CoolSet<Type>&); // Intersection of two sets
  146.   
  147.   Boolean next_union (CoolSet<Type>&);        // Return next union item
  148.   Boolean next_difference (CoolSet<Type>&);    // Return next difference item
  149.   Boolean next_xor (CoolSet<Type>&);        // Return next exclusive-or
  150.   Boolean next_intersection (CoolSet<Type>&);    // Return next intersection
  151.   
  152.   friend ostream& operator<< (ostream&, const CoolSet<Type>&); // Overload output
  153.   inline friend ostream& operator<< (ostream&, const CoolSet<Type>*); 
  154.  
  155.   Boolean operator== (const CoolSet<Type>&) const; // Set equality test
  156.   inline Boolean operator!= (const CoolSet<Type>&) const; // Set inequality test
  157.   
  158.   inline void set_hash (Type##_CoolSet_Hash);    // Set the hash function
  159.   void set_compare (Type##_CoolSet_Item_Compare = NULL); // Set compare function
  160.  
  161. private:
  162.   Type next_data;                // Slot to hold next_union data
  163.   Type##_bucket* table;                // Pointer to key buckets
  164.   Type##_CoolSet_Hash h_function;        // Pointer to hash function
  165.   Type##_CoolSet_Item_Compare compare;        // Pointer operator== function
  166.   friend Boolean Type##_CoolSet_are_keys_equal (const Type&, const Type&);
  167.   friend long Type##_CoolSet_default_hash (const Type&);
  168.   
  169.   Boolean do_find (const Type&) const;        // CoolSet current position
  170. };
  171.  
  172. // Avoid deep copy, and do set operations in place with envelope
  173.  
  174. template<class Type> CoolSet {
  175. typedef int ________int;            // Coolcpp hack, get rid off it soon
  176.  
  177. #define ENVELOPE_VERTICAL            // |= can be done in place
  178. #define ENVELOPE_AMPERSAND            // &= can be done in place
  179. #define ENVELOPE_MINUS                // -= can be done in place
  180. #define ENVELOPE_CARET                // ^= can be done in place
  181.  
  182. #define CoolLetter CoolSet<Type>
  183. #define CoolEnvelope CoolSet_##Type##E        // for Coolcpp parsing
  184.  
  185. #include <cool/Envelope.h>            // Include envelope macros
  186.  
  187. #define ENVELOPE_VERTICAL    
  188. #define ENVELOPE_AMPERSAND    
  189. #define ENVELOPE_MINUS        
  190. #define ENVELOPE_CARET        
  191.  
  192. #undef CoolLetter
  193. #undef CoolEnvelope
  194. }
  195.  
  196. // operator=  -- Assignment from an envelope back to real set
  197. // Input:     envelope reference
  198. // Output:    Set reference with contents in envelope being swapped over
  199.  
  200. template<class Type>
  201. inline CoolSet<Type>& CoolSet<Type>::operator= (CoolSet<Type>E& env){
  202.   env.shallow_swap((CoolSet<Type>E*)this, &env); // same physical layout
  203.   return *this;
  204. }
  205.  
  206.  
  207. // set_union -- Determine the union of two sets
  208. // Input:       Reference to a Bit Set object
  209. // Output:      None
  210.  
  211. template <class Type> 
  212. inline void CoolSet<Type>::set_union (const CoolSet<Type>& b) {
  213.   this->operator|= (b);
  214. }
  215.  
  216.  
  217. // set_difference -- Determine the difference of two sets
  218. // Input:            Reference to a Bit Set object
  219. // Output:           None
  220.  
  221. template <class Type> 
  222. inline void CoolSet<Type>::set_difference (const CoolSet<Type>& b) {
  223.   this->operator-= (b);
  224. }
  225.  
  226.  
  227. // set_xor -- Determine the exclusive-OR of two sets
  228. // Input:     Reference to a Bit Set object
  229. // Output:    None
  230.  
  231. template <class Type> 
  232. inline void CoolSet<Type>::set_xor (const CoolSet<Type>& b) {
  233.   this->operator^= (b);
  234. }
  235.  
  236.  
  237. // set_intersection -- Determine the intersection of two sets
  238. // Input:              Reference to a Bit Set object
  239. // Output:             None
  240.  
  241. template <class Type> 
  242. inline void CoolSet<Type>::set_intersection (const CoolSet<Type>& b) {
  243.   this->operator&= (b);
  244. }
  245.  
  246.   
  247. // operator!= -- Return logical result of not equal comparison test
  248. // Input:        Reference to another Bit Set object
  249. // Output:       Boolean TRUE/FALSE
  250.  
  251. template <class Type> 
  252. inline Boolean CoolSet<Type>::operator!= (const CoolSet<Type>& b) const {
  253.   return (!(this->operator== (b)));
  254. }
  255.  
  256.  
  257. // Set_hash -- Set the hash function for this instance
  258. // Input:      Pointer to hash function
  259. // Output:     None
  260.  
  261. template <class Type> 
  262. inline void CoolSet<Type>::set_hash (Type##_CoolSet_Hash h) {
  263.   this->h_function = h;
  264. }
  265.  
  266.  
  267. // 
  268. // // operator| -- Return the union of two sets, that is all elements in each set
  269. // // Input:       Reference to a set
  270. // // Output:      New Set object containing union of two sets
  271. // 
  272. // template <class Type> CoolSet {
  273. // inline CoolSet<Type> operator| (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  274. //   CoolSet<Type> result(s1);            // Temporary variable
  275. //   result.operator|=(s2);            // Mutate temp with union
  276. //   return result;                // Return resulting union
  277. // }}
  278. // 
  279. // 
  280. // // operator- -- Return the difference of two sets, that is all elements in
  281. // //              the first set that are not in the second
  282. // // Input:       Reference to a set
  283. // // Output:      New CoolSet object containing difference of two sets
  284. // 
  285. // template <class Type> CoolSet{
  286. // inline CoolSet<Type> operator- (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  287. //   CoolSet<Type> result(s1);            // Temporary variable
  288. //   result.operator-=(s2);            // Mutate temp with difference
  289. //   return result;                // Return resulting union
  290. // }}
  291. // 
  292. // 
  293. // // operator^ -- Return the exclusive-OR of two sets, that is all elements in
  294. // //              the first set that are not in the second and all elements in the
  295. // //              second set that are not in the first
  296. // // Input:       Reference to set
  297. // // Output:      New CoolSet object containing XOR of two sets
  298. // 
  299. // template <class Type> CoolSet {
  300. // inline CoolSet<Type> operator^ (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  301. //   CoolSet<Type> result(s1);            // Temporary variable
  302. //   result.operator^=(s2);            // Mutate temp with xor
  303. //   return result;                // Return resulting xor
  304. // }}
  305. // 
  306. // 
  307. // // operator& -- Return the intersection of two sets, that is all elements that
  308. // //              are in both sets
  309. // // Input:       Reference to CoolSet object
  310. // // Output:      New CoolSet object containing intersection of two sets
  311. // 
  312. // template <class Type> CoolSet {
  313. // inline CoolSet<Type> operator& (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  314. //   CoolSet<Type> result(s1);            // Temporary variable
  315. //   result.operator&=(s2);            // Mutate with intersection
  316. //   return result;                // Return resulting intersection
  317. // }}
  318.  
  319.  
  320. // next_intersection -- Position at the next intersection of two Sets.
  321. // Input:               Reference to CoolSet object
  322. // Output:              TRUE/FALSE, current position updated
  323.  
  324. template <class Type> 
  325. Boolean CoolSet<Type>::next_intersection (CoolSet<Type>& s) {
  326.   if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
  327.     return FALSE;                // Indicate no more elements
  328.   while (this->next () == TRUE)    {        // While there are elements
  329.     if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
  330.       return FALSE;                // Return failure status
  331.     if (s.find(this->value()) == TRUE)        // If element in 2nd set
  332.       return TRUE;                // Return success status
  333.   }
  334.   this->curpos = INVALID;            // Invalidate current position
  335.   return FALSE;                    // Return failure status
  336. }
  337.  
  338.  
  339. // next_union -- Position at the next union of two Sets.
  340. // Input:        Reference to CoolSet object
  341. // Output:       TRUE/FALSE, current position updated
  342.  
  343. template <class Type> 
  344. Boolean CoolSet<Type>::next_union (CoolSet<Type>& s) {
  345.   if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
  346.       this->curpos == INVALID) {
  347.     if (this->next () == TRUE)            // If more elements in 1st set
  348.       return TRUE;                // Return success status
  349.     else                    // Else set traversed flag
  350.       this->curpos = SET_TRAVERSED(TRUE);
  351.   }
  352.   while (s.next () == TRUE) {            // While more elements in 2nd 
  353.     if (this->find(s.value()) == FALSE) {    // If element not in 1st set
  354.       this->curpos |= SET_TRAVERSED(TRUE);    // Reset flag zeroed by find
  355.       this->next_data = s.value();        // Refer to next piece of data
  356.       return TRUE;                // Return success status
  357.     }
  358.   }
  359.   this->curpos = INVALID;            // Invalidate current position
  360.   return FALSE;                    // Return failure status
  361. }
  362.  
  363.  
  364. // next_difference -- Position at the zero-relative integer of the next bit in 
  365. //                    the difference of two CoolSets.
  366. // Input:             Reference to CoolSet object
  367. // Output:            TRUE/FALSE, current position updated
  368.  
  369. template <class Type> 
  370. Boolean CoolSet<Type>::next_difference (CoolSet<Type>& s) {
  371.   if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
  372.     return FALSE;                // Indicate no more elements
  373.   while (this->next () == TRUE)    {        // While there are elements
  374.     if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
  375.       return FALSE;                // Return failure status
  376.     if (s.find(this->value()) == FALSE)        // If element not in 2nd set
  377.       return TRUE;                // Return success status
  378.   }
  379.   this->curpos = INVALID;            // Invalidate current position
  380.   return FALSE;                    // Return failure status
  381. }
  382.  
  383.  
  384. // next_xor -- Position at the zero-relative integer of the next bit in 
  385. //             the XOR of two Sets.
  386. // Input:      Reference to CoolSet object
  387. // Output:     TRUE/FALSE, current position updated
  388.  
  389. template <class Type> 
  390. Boolean CoolSet<Type>::next_xor (CoolSet<Type>& s) {
  391.   if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
  392.       this->curpos == INVALID) {
  393.     if (this->next_difference (s) == TRUE)    // If more elements in 1st set
  394.       return TRUE;                // Return success status
  395.     else {                    // Else set traversed flag
  396.       this->curpos = SET_TRAVERSED(TRUE);
  397.       s.reset();                // Reset current position
  398.     }
  399.       }
  400.   if ((s.curpos != INVALID && !TRAVERSED(s.curpos)) || s.curpos == INVALID) {
  401.     this->reset();                // Reset 1st set pointer
  402.     if (s.next_difference (*this)) {        // If any other elements in 2nd
  403.       this->curpos |= SET_TRAVERSED(TRUE);    // Reset flag set by find
  404.       this->next_data = s.value();        // Save data for value()
  405.       return TRUE;                // Return success status
  406.     }
  407.   }
  408.   this->curpos = INVALID;            // Invalidate current position
  409.   return FALSE;                    // Return failure status
  410. }
  411.  
  412.  
  413. // operator<< -- Overload the output operator to provide a crude print
  414. //               capability for CoolSet objects
  415. // Input:        ostream reference, CoolSet pointer
  416. // Output:       None
  417.  
  418. template <class Type> CoolSet {
  419. inline ostream& operator<< (ostream& os, const CoolSet<Type>* s) {
  420.   return operator<< (os, *s);
  421. }
  422. }
  423.  
  424.  
  425. #endif                        // End of SETH
  426.